package leetcode.code2434;

import java.util.Stack;

public class Solution {

	public String robotWithString(String s) {
		int[] hash = new int[26];
		for (int i = 0; i < s.length(); i++) {
			hash[s.charAt(i) - 'a']++;
		}
		Stack<Integer> stack = new Stack<>();
		int p = 0;
		StringBuffer ans = new StringBuffer();
		while (p < s.length()) {
			int c = s.charAt(p) - 'a';
			hash[c]--;
			stack.add(c);
			int min = -1;
			for (int i = 0; i < hash.length; i++) {
				if (hash[i] != 0) {
					min = i;
					break;
				}
			}
			while (!stack.isEmpty() && (min == -1 || stack.peek() <= min)) {
				ans.append((char) (stack.pop() + 'a'));
			}
			p++;
		}
		return ans.toString();
	}

}
